Майнор "Интеллектуальный анализ данных"

Курс "Введение в анализ данных"

Лабораторная работа №2. Кластерный анализ.

Часть 1

В данном задании вам необходимо самостоятельно реализовать один из алгоритмов кластеризации.
По аналогии с классами в scikit-learn, нужно реализовать класс, наследуемый от Base Estimator.
Подробнее про реализацию своих моделей в scikit-learn: here.
В классе помимо __init__() нужно реализовать два метода:

Для удобства можно создавать дополнительные методы класса, которые будут вызываться в fit() или predict().
Функции для вычисления расстояний между объектами самим реализовывать не нужно, используйте реализации из scipy.

Пример использования матрицы расстояния:

Вариант №1

Алгоритм агломеративной кластеризации.

Параметры:

Атрибуты:

Дополнительно нужно реализовать метод get_labels() для вычисления labels_, он должен быть аналогичен fcluster().
В случае, если n_clusters не None, то после вычисления матрицы z_ в методе fit() должен быть вызван get_labels() с соответствующими параметрами, и вычислены labels_. В других случаях метод fit() только вычисляет матрицу z_, для вычисления labels_ нужно явно вызывать get_labels().

Метод predict(): Кластер для нового объекта определяется по методу, заданному в linkage.
Note: Метод predict() не выполняется в случае, когда metric - это матрица расстояний.

Вариант №2

Алгоритм Dbscan.

Параметры:

Атрибуты:

Метод predict(): Для нового объекта вычисляется число основных точек из каждого кластера, попавших в окрестность $\varepsilon$. Объект определяется в кластер с наибольшим числом таких точек.
Note: Метод predict() не выполняется в случае, когда metric - это матрица расстояний.

Вариант №3

Алгоритм K-Means.

Параметры:

Атрибуты:

Метод predict(): Новый объект определяется в кластер, центр которого расположен ближе всех к этому объекту.

Тестирование

Вашу реализацию необходимо сравнить с питоновской реализацией алгоритма из sklearn или scipy. Результаты кластеризации должны совпадать.
Также необходимо сравнить скорость работы вашей реализации и питоновской (это нормально, если ваша реализация будет медленнее).
Сравнение необходимо выполнить на наборе данных iris.

Как можно видеть, ARI равен 1 => алгоритмы работают одинаково

Проверим, как работает механика предсказания. Пусть нам пришли данные, идентичные некоторым строчкам. Результат предсказаний должен совпадать с соответсвующими ярлыками кластеров

Как можно видеть, лейблы действительно совпадают, а значит механика предсказания работает корректно

Бонусное

Дополнительно вы можете поработать над эффективностью алгоритма по скорости и памяти, добавить поддержку многопоточности, или расширить базовый функционал.

Распределение по вариантам

Вариант №1

Вариант №2

Вариант №3

Часть 2

В данном задании вам предлагается проанализировать набор данных по различным городам США. Каждый город характеризуется следующими признаками:

Notes:


Задания:

  1. Выполните необходимую предобработку данных. Перед кластеризацией исключите из данных признаки Place, Long и Lat.
  1. Выполните кластеризацию иерархическим методом.
    Рассмотрите различные расстояния между объектами. Определите, какие следует использовать при кластеризации.
    Выполните кластеризацию с различными расстояниями между кластерами. Сравните результаты, сделайте выводы.

Можно видеть, что большинство метрик поступают одинаково. Поэтому пусть будем использовать классическую метрику расстояния Евклида

Тут методы дают совершенно разные варианты. Будем использовать ward-метод, т.к. есть хорошо выраженные расстояния между кластерами

  1. Выполните кластеризацию методом Dbscan. Используйте расстояния между объектами, определенные в предыдущем пункте.
    Реализуйте эвристику (см. лекции) для выбора параметров алгоритма. Подберите подходящие параметры алгоритма.

По методу каменистой осыпи (или локтя) можно определить, что оптимальным eps будет 0.35, а min_samples выставим 2

  1. Выполните кластеризацию методом kmeans. Определите наилучшее (на ваш взгляд) число кластеров.

По методу локтя выберем число кластеров, равное 5

  1. (Бонусное) Выполните кластеризацию другими методами. Например, HDBSCAN или алгоритмы, реализованные в scikit-learn.
  1. В результате выполнения предыдущих пунктов вы должны получить 4 или больше разбиений объектов (по одному на каждый метод). Сравните их между собой, сделайте выводы о сходствах и различиях.
    Оцените результаты каждой кластеризации, используя метрики, рассмотренные на занятиях (Silhouette и прочие).

Как можно видеть, разные алгоритмы создают разное количество кластеров

Сравним алгоритмы по скорости обучения:

На текущих данных получилось так, что AgglomerativeClustering самый быстрый алгоритм

По метрике силуэта получилось, что лучшую кластеризацию провёл DBSCAN

Однако при рассмотрении визуализации силуэта видно, что лучше получилось у алгоритмов AgglomerativeClustering и KMeans

  1. Выберите одно разбиение, наиболее подходящее на ваш взгляд. Предложите интерпретацию полученным кластерам или покажите, что этого сделать нельзя.

В качестве лучшего разбиения выберем AgglomerativeCLustering

Можно видеть, что многие точки, соответствующие одному кластеру, действительно группируются в определённые "кучки". Однако выделить хоть на каком-либо графике области, по которым можно визуально определить кластеры, нельзя, т.к. точки разных цветов сильно перемешаны.

Однако, согласно TSNE, кластеризация получилась вполне качественная, но определить "на глаз" скопления данных не получается

  1. Оцените, как полученные кластеры распределены географически.
    Оцените, как полученные кластеры распределены по штатам. Можно ли выделить какую-то зависимость (территориальную или для штатов)?
    (Бонусное) Провизуализируйте распределение на карте США.

Как показано выше, большая часть определённых мест относится к штатам Техас, Флорида, Калифорния и Нью-Йорк

Однако стоит иметь ввиду, что в принципе городов из Техаса, Калифорнии, Флориды и Нью-Йорка больше, чем всех остальных

Покажем, как города распределены на карте